package com.wm.algorithm.math;

/**
 * @ClassName: SimpleMath
 * @Description: 简单数学运算
 * @Author: Deamer
 * @Date: 2023/3/21 22:57
 */
public class SimpleMath {

    /**
     * 青蛙跳台(斐波那契)
     * 题目：一只青蛙可以跳上一级台阶，两级台阶，三级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法？
     * 方法3：动态规划（推荐）
     * 思路：找规律，先找到4级台阶分别跳法是什么，然后当前跳的步数和前面3次的跳跃数是有关系的（前3个值之和）
     */
    // O(n)/O(n)
    public int frogSkip3(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }

    /**
     * 青蛙跳台
     * 题目：一只青蛙可以跳上一级台阶，两级台阶，三级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法？
     * 方法2：记忆化搜索
     * 思路：方法1中，存在很多重复计算，例如 假设n=4；f[4] = f[3]+f[2]=f[1]+f[2]+f[2];
     * 其实可以看到，把f[3]分解成f[1]+f[2]后，再计算后面的f[2]就重复了。为了改进，我们把计算过
     * 的保存下来，使用数组集合即可。
     */
    // O(n)/O(n)
    public int frogSkip2(int n) {
        int[] memo = new int[n + 1];
        return jumpSum(n, memo);
    }

    private int jumpSum(int n, int[] memo) {
        if (n <= 2) {
            return n;
        }
        if (n == 3) {
            return 4;
        }
        if (memo[n] != 0) {
            // 如果数组中已经存在某个运算结果，直接调用即可
            return memo[n];
        }
        return jumpSum(n - 1, memo) + jumpSum(n - 2, memo) + jumpSum(n - 3, memo);
    }

    /**
     * 青蛙跳台(斐波那契)
     * 题目：一只青蛙可以跳上一级台阶，两级台阶，三级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法？
     * 方法1：暴力破解
     * 思路：找规律，先找到4级台阶分别跳法是什么，然后暴力破解，递归实现
     */
    // O(2^n)/O(n):递归栈的空间
    public int frogSkip(int n) {
        if (n <= 2) {
            return n;
        }
        if (n == 3) {
            return 4;
        }
        return frogSkip(n - 1) + frogSkip(n - 2) + frogSkip(n - 3);
    }

    /**
     * 509. 斐波那契数
     * https://leetcode.cn/problems/fibonacci-number/
     * 方法：DP表+状态转移方程
     * 思路：DP表只记录必要的数据，必要的数据就是前两个数【降低时间时间复杂度】，第2个值覆盖第1个值，将前两个值之和覆盖第2个值，依次滚动。
     *
     * @param n
     * @return
     */
    // O(n)/O(1)
    public int fib(int n) {
        if (n == 0 || n == 1) {
            // base case
            return n;
        }
        // 分别代表 dp[i - 1] 和 dp[i - 2]
        int dp1 = 0, dp2 = 1;
        for (int i = 2; i <= n; i++) {
            // dp[i] = dp[i - 1] + dp[i - 2];
            int dpi = dp1 + dp2;
            // 滚动更新
            dp1 = dp2;
            dp2 = dpi;
        }
        return dp2;
    }

    /**
     * 9. 回文数
     * https://leetcode.cn/problems/palindrome-number/description/?show=1
     * 方法：数学运算
     * 思路：将数字从后一位往前计算出一个数字y，同时x数字每次都/10，即减少末位，直到x==y循环结束
     *
     * @param x
     * @return
     */
    // O(logn)/O(1) 对于每次迭代，我们会将输入除以10，因此时间复杂度为 O(logn)/我们只需要常数空间存放若干变量
    public boolean isPalindrome2(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        int y = 0;
        while (x > y) {
            y = y * 10 + x % 10;
            x /= 10;
        }
        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == y || (x == y / 10);
    }
}
